home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / intrvews / xgrab.lha / xgrab / grabst / layout.c < prev    next >
C/C++ Source or Header  |  1990-03-06  |  31KB  |  1,236 lines
  1. /**
  2.    GRAB Graph Layout and Browser System
  3.  
  4.    Copyright (c) 1986, 1988 Regents of the University of California
  5.    Copyright (c) 1989, Tera Computer Company
  6.  **/
  7.  
  8.   /**
  9.      layout.c contains procedures to position the vertices on each level of 
  10.      a digraph.
  11.    **/
  12.  
  13. #include "malloc.h"
  14. #include "attribute.h"
  15. #include "digraph.h"
  16. #include "debug.h"
  17.  
  18. #define    MIN_X        0    /* minimum x-position */
  19. #define    MAX_X        10000 * HALF_CHAR    /* maximum x-position */
  20.  
  21. #define    MIN_OFFSET    20 * HALF_CHAR    /* minimum offset between levels */
  22. #define    MAX_OFFSET    2 * MIN_OFFSET    /* maximum offset between levels */
  23. #define MAX_OFFSET_PERCENT    0.34
  24.  
  25. #define    MAX_PRIORITY    MAXNODES
  26.  
  27. #define    PARTIAL        1    /* partial layout of level (dummies done) */
  28. #define    FULL        2    /* full layout, including dummies */
  29.  
  30. typedef struct plist PLIST;    /* priority list of members */
  31. struct plist
  32. {
  33.     MEMBER *member;
  34.     PLIST *next;
  35. };
  36.  
  37. #define each_member_by_priority(plist, member)    \
  38.     { PLIST *p;\
  39.       for (p = plist; p != NULL; p = p->next)\
  40.       {\
  41.          member = p->member; 
  42.  
  43. #define abs(_x) \
  44.      ( (_x) > 0 ? (_x) : -(_x) )
  45.  
  46. PLIST *sort_by_priority();
  47. NODE *prev_dummy();
  48. NODE *next_dummy();
  49. float up_down_bc();
  50. BOOL do_straighten(), do_vertical();
  51.  
  52. layout_levels(digraph)
  53. DIGRAPH *digraph;
  54.   /**
  55.      layout_levels uses the priority layout method to determine the x-
  56.      coordinates of each member of each level of digraph.
  57.    **/
  58. {
  59.     fix_all_positions(digraph);       /* determine the initial positions */
  60.     straighten_all_dummies(digraph);  /* line up dummy nodes vertically */
  61.     compute_barycenters(digraph);     /* compute new barycenters */
  62.     compute_priorities(digraph);      /* compute the priorities of each node */
  63.  
  64.     if (debug)
  65.     {
  66.         printf("layout_levels:\n");
  67.         offset_levels(digraph);         /* determine offset between levels */
  68.         compute_y_positions(digraph);  /* put y value into each node */
  69.     }
  70.  
  71.     layout_by_bc(digraph, UPDOWN, PARTIAL, 1);  
  72.                     /* layout levels 1..last by up-bc */
  73.     layout_one_level(digraph, First_level(digraph), PARTIAL, DOWN);
  74.                        /* adjust top level */
  75.     layout_one_level(digraph, Last_level(digraph), PARTIAL, UP);
  76.                       /* adjust bottom level */
  77.     offset_levels(digraph);                /* determine offset between levels */
  78.     compute_y_positions(digraph);          /* put y value into each node */
  79.     straighten_all_edges(digraph, straightenEdges);     
  80.                           /* remove bends in long edges */
  81. } /* layout_levels */
  82.  
  83. quick_layout_levels(digraph)
  84. DIGRAPH *digraph;
  85.   /**
  86.      quick_layout_levels does the minimal possible layout of the digraph by
  87.      spreading out the nodes on each level and by determining the y positions
  88.      of each level and node.
  89.    **/
  90. {
  91.     fix_all_positions(digraph);       /* determine the initial positions */
  92.     offset_levels(digraph);              /* determine offset between levels */
  93.     compute_y_positions(digraph);      /* put y value into each node */
  94. } /* quick_layout_levels */
  95.  
  96. mid_level(digraph)
  97. DIGRAPH *digraph;
  98.   /**
  99.      mid_level returns the level number of the middle level of digraph.
  100.    **/
  101. {
  102.    return(Lno(Last_level(digraph)) / 2);
  103. } /* mid_level */
  104.  
  105.  
  106. fix_all_positions(digraph)
  107. DIGRAPH *digraph;
  108.   /**
  109.      fix_all_positions fixes the positions of each node in digraph by
  110.      spacing the nodes according to their widths.
  111.    **/
  112. {
  113.     LEVEL *level;       /* each level */
  114.     int x_max;           /* maximum x in digraph */
  115.     int x_level;    /* maximum x on a level */
  116.  
  117.     x_max = 0;
  118.  
  119.     each_level(digraph, level)
  120.     loop
  121.         x_level = fix_positions(level);
  122.  
  123.         if (x_level > x_max)
  124.     {
  125.         x_max = x_level;
  126.     }
  127.     endloop
  128.  
  129.     each_level(digraph, level)
  130.     loop
  131.         spread_positions(level, x_max);
  132.     endloop
  133.  
  134. } /* fix_all_positions */
  135.  
  136.  
  137. fix_positions(level)
  138. LEVEL *level;
  139.   /**
  140.      fix_positions fixes the positions of each node in level by
  141.      spacing the nodes according to their widths.  It returns
  142.      the x-value of the last node (including gap on right side).
  143.    **/
  144. {
  145.     MEMBER *member; /* each member */
  146.     int prev_pos;   /* each previous position */
  147.  
  148.     prev_pos = MIN_X;
  149.  
  150.     each_member(level, member)
  151.     loop
  152.         X_position(member) = prev_pos + GAP/2 + Half_width(member);
  153.         prev_pos = X_right(member) + GAP/2;
  154.     endloop
  155.  
  156.     return (prev_pos);    /* return largest x on level */
  157. } /*  fix_positions */
  158.  
  159. spread_positions(level, x_max)
  160. LEVEL *level;
  161. int x_max;        /* maximum x-value of level */
  162.   /**
  163.      spread_positions spreads the nodes in each level evenly between 0
  164.      and x_max, starting at the left.  If the optimal space is already
  165.      occupied by a previous node, the current node is moved as far left
  166.      as possible.
  167.    **/
  168. {
  169.     MEMBER *member; /* each member */
  170.     int prev_pos;   /* each previous position */
  171.     int intervals;  /* number of divisions on the level */
  172.     int i;       /* counter */
  173.  
  174.     intervals = card(Members(level)) + 1;
  175.     prev_pos = MIN_X;
  176.     i = 0;
  177.  
  178.     each_member(level, member)
  179.     loop
  180.         i += 1;
  181.         X_position(member) = MAX(((x_max * i) / intervals),
  182.                            (prev_pos + GAP/2 + Half_width(member)));
  183.         prev_pos = X_right(member) + GAP/2;
  184.     endloop
  185. } /* spread_positions */
  186.  
  187. compute_priorities(digraph)
  188. DIGRAPH *digraph;
  189.   /**
  190.      compute_priorities computes the up, down, and updown priorities for each 
  191.      node of each level of digraph.
  192.    **/
  193. {
  194.     LEVEL *level;    /* each level */
  195.     MEMBER *member;  /* each member */
  196.  
  197.     if (debug)
  198.     {
  199.         printf("\ncompute_priorities:\n");
  200.     }
  201.  
  202.     each_level(digraph, level)
  203.     loop
  204.         each_member(level, member)
  205.         loop
  206.         if (Is_dummy(member))
  207.             /* give it the highest priority */
  208.         {
  209.             Priority(member, UP) = MAX_PRIORITY;
  210.             Priority(member, DOWN) = MAX_PRIORITY;
  211.         }
  212.         else
  213.         {
  214.             Priority(member, UP) = card(Ante_set(Member_node(member)));
  215.             Priority(member, DOWN) = card(Succ_set(Member_node(member)));
  216.         }
  217.  
  218.           /* updown priority is just the average of the two */
  219.         Priority(member, UPDOWN) = (Priority(member, UP) + 
  220.                     Priority(member, DOWN)) / 2;
  221.  
  222.         if (debug)
  223.         {
  224.             printf("   %s:  (%d, %d %d)\n", Name(Member_node(member)),
  225.                Priority(member, UP), Priority(member, DOWN),
  226.                Priority(member, UPDOWN));
  227.         }
  228.         endloop
  229.     endloop
  230. } /* compute_priorities */
  231.  
  232. layout_by_bc(digraph, direction, mode, levnum)
  233. DIGRAPH *digraph;
  234. DIRECTION direction;
  235. int mode;        /* FULL or PARTIAL layout mode */
  236. int levnum;
  237.   /**
  238.      layout_by_bc positions the nodes in each level of digraph as close to its
  239.      up (direction == UP) or down (direction == DOWN) barycenters as possible.
  240.      The bc's of the previous and next levels of each level are recomputed
  241.      if the positions of nodes are changed.  Levnum is first (direction = UP) 
  242.      or last (direction = DOWN) level to layout.
  243.    **/
  244. {
  245.     LEVEL *level;    /* each level */
  246.  
  247.     switch (direction)
  248.     {
  249.         case UP:  /* layout from given level to last, by up barycenters */
  250.         each_level(digraph, level)
  251.         loop
  252.             if (Lno(level) >= levnum)   /* layout this level */
  253.         {
  254.                 layout_one_level(digraph, level, mode, UP);
  255.         }
  256.         endloop
  257.         break;
  258.  
  259.         case DOWN:  /* layout from last level to given, by down barycenters */
  260.         each_level_reverse(digraph, level)
  261.  
  262.         loop
  263.             if (level == Last_level(digraph))
  264.         {
  265.                 continue;
  266.         }
  267.  
  268.             if (Lno(level) >= levnum)   /* layout this level */
  269.         {
  270.                 layout_one_level(digraph, level, mode, DOWN);
  271.         }
  272.         endloop
  273.         break;
  274.  
  275.         case UPDOWN:  /* layout first to last to first, by average bc */
  276.         each_level(digraph, level)
  277.         loop
  278.             layout_one_level(digraph, level, mode, UPDOWN);
  279.         endloop
  280.  
  281.         each_level_reverse(digraph, level)
  282.         loop
  283.             layout_one_level(digraph, level, mode, UPDOWN);
  284.         endloop
  285.         break;
  286.     }
  287.  
  288.     if (debug)
  289.     {
  290.         printf("\nlayout_by_bc:  %s\n", 
  291.            (direction == UP) ? "UP" : ((direction == DOWN) ? 
  292.                        "DOWN" : "UPDOWN"));
  293.         offset_levels(digraph);            /* determine offset between levels */
  294.         compute_y_positions(digraph);      /* put y value into each node */
  295.     }
  296. } /* layout_by_bc */
  297.  
  298. layout_one_level(digraph, level, mode, direction)
  299. DIGRAPH *digraph;
  300. LEVEL *level;
  301. int mode;    /* FULL or PARTIAL layout (if dummies already laid out) */
  302. DIRECTION direction;
  303.   /**
  304.       layout_one_level positions the nodes in level as close as possible to 
  305.       their up (direction == UP) or down (direction == down) barycenters.
  306.       The bc's of the previous and next levels of level are recomputed.
  307.    **/
  308. {
  309.     MEMBER *member;  /* each member */
  310.     PLIST *plist;    /* members sorted by priority */
  311.     int shift;       /* amount to shift each member */
  312.     float bc;
  313.  
  314.     plist = sort_by_priority(level, direction);
  315.       /**
  316.          NOTE:  the above is incredibly wasteful, since this is done
  317.          on each iteration, and the priorities are static.
  318.        **/
  319.  
  320.     each_member(level, member)
  321.     loop
  322.         if (mode == FULL)
  323.     {
  324.             Is_layed(member) = FALSE;    /* not layed out yet */
  325.     }
  326.         else
  327.         {
  328.         if (Is_dummy(member) &&
  329.          (Is_dummy(prev_dummy(digraph, member)) || 
  330.          Is_dummy(next_dummy(digraph, member))) )
  331.         {
  332.             Is_layed(member) = TRUE;
  333.         }
  334.         else
  335.         {
  336.             Is_layed(member) = FALSE;
  337.         }
  338.         }
  339.     endloop
  340.  
  341.     each_member_by_priority(plist, member)
  342.     loop
  343.         if (direction == UPDOWN)
  344.     {
  345.         bc = up_down_bc(member);
  346.     }
  347.         else
  348.     {
  349.         bc = Bc(member, direction);
  350.     }
  351.  
  352.         if (bc == NO_BC)    /* leave it alone */
  353.     {
  354.         continue;
  355.     }
  356.  
  357.         if (Is_layed(member))
  358.     {
  359.         continue;
  360.     }
  361.  
  362.         shift = (int) bc - X_position(Member_node(member));
  363.  
  364.         if (shift < 0)    /* shift left */
  365.     {
  366.         shift_left(member, (int) bc);
  367.     }
  368.         else if (shift > 0)    /* shift right */
  369.     {
  370.         shift_right(member, (int) bc);
  371.     }
  372.  
  373.         Is_layed(member) = TRUE;        /* layed out now */
  374.  
  375.         if (debug)
  376.         {
  377.         printf("\nlayout_one_level:  layed out %s:  ", 
  378.            Name(Member_node(member)));
  379.         printf("Bc(%s) = %1.2f, X_position = %d\n", 
  380.            (direction == UP) ? "UP": ((direction == DOWN) ?
  381.                           "DOWN" : "UPDOWN"),
  382.            Bc(member, direction % 2), X_position(member));
  383.  
  384.         if (Prev_level(level) != NULL)   
  385.         /* recompute down-bc of prev level */
  386.         {
  387.             compute_bc_level(digraph, Prev_level(level), DOWN);
  388.         }
  389.  
  390.         if (Next_level(level) != NULL)   /* recompute up-bc of next level */
  391.         {
  392.             compute_bc_level(digraph, Next_level(level), UP);
  393.         }
  394.         offset_levels(digraph);      /* determine offset between levels */
  395.         compute_y_positions(digraph); /* put y value into each node */
  396.         }
  397.     endloop
  398.  
  399.     dispose_plist(plist);   /* recycle */
  400.  
  401.       /* now recompute bc's of affected levels */
  402.     if (Prev_level(level) != NULL)   /* recompute down-bc of prev level */
  403.     {
  404.         compute_bc_level(digraph, Prev_level(level), DOWN);
  405.     }
  406.  
  407.     if (Next_level(level) != NULL)   /* recompute up-bc of next level */
  408.     {
  409.         compute_bc_level(digraph, Next_level(level), UP);
  410.     }
  411. } /* layout_one_level */
  412.  
  413. shift_left(member, new_x)
  414. MEMBER *member;       /* member to shift */
  415. int new_x;            /* new position for member */
  416.   /**
  417.      shift_left shifts member left to new_x.  If The left is blocked by a 
  418.      layed-out member, then member is moved as close as possible to new_x.
  419.    **/
  420. {
  421.     MEMBER *blocker;       /* layed-out member to left */
  422.     MEMBER *first;    /* first member to shift left */
  423.     MEMBER *prev;    /* each previous member on level */
  424.     int min_x;        /* minimum left position */
  425.     int prev_pos;    /* position of each previous member */
  426.  
  427.       /* first find the member to the left with a higher priority */
  428.     for (first = member, blocker = Prev_member(member); 
  429.       (blocker != NULL) && !Is_layed(blocker);
  430.       first = blocker, blocker = Prev_member(blocker))
  431.     {}
  432.  
  433.     if (blocker == NULL)   /* shift as little as possible */
  434.     {
  435.         min_x = MIN_X + GAP/2;
  436.     }
  437.     else   /* stop at blocker */
  438.     {
  439.         min_x = X_right(blocker) + GAP/2;
  440.     }
  441.  
  442.       /* now shift all previous members left as much as possible */
  443.     prev_pos = min_x;   /* initial position */
  444.  
  445.     for (prev = first; prev != Next_member(member); prev = Next_member(prev))
  446.     {
  447.         X_position(prev) = prev_pos + GAP/2 + Half_width(prev);
  448.         prev_pos = X_right(prev) + GAP/2;
  449.     }
  450.  
  451.       /**
  452.      We may have just shifted too far.  Shift members back to the 
  453.      right if possible
  454.        **/
  455.     if (X_position(member) < new_x)     
  456.     {
  457.         X_position(member) = new_x;
  458.     prev_pos = X_left(member) - GAP/2;
  459.  
  460.     for (prev = Prev_member(member); prev != blocker; 
  461.          prev = Prev_member(prev))
  462.     {
  463.             X_position(prev) = prev_pos - GAP/2 - Half_width(prev);
  464.             prev_pos = X_left(prev) - GAP/2;
  465.     }
  466.     }
  467. } /* shift_left */
  468.  
  469.  
  470. shift_right(member, new_x)
  471. MEMBER *member;       /* member to shift */
  472. int new_x;            /* new position for member */
  473.   /**
  474.      shift_right shifts member right to new_x.  If the right is blocked by a 
  475.      layed-out member, then member is moved as close as possible to new_x.
  476.    **/
  477. {
  478.     MEMBER *blocker;    /* first layed-out member to the right */
  479.     MEMBER *first;    /* first member to shift right */
  480.     MEMBER *next;    /* each next member on level */
  481.     int max_x;        /* maximum right position */
  482.     int prev_pos;    /* position of each previous member */
  483.  
  484.       /* first find the member to the right with a higher priority */
  485.     for (first = member, blocker = Next_member(member);
  486.       (blocker != NULL) && !Is_layed(blocker);
  487.       first = blocker, blocker = Next_member(blocker))
  488.     {}
  489.  
  490.     if (blocker == NULL)   /* stop at right edge */
  491.     {
  492.         max_x = MAX_X - GAP/2;
  493.     }
  494.     else   /* stop at blocker */
  495.     {
  496.         max_x = X_left(blocker) - GAP/2;
  497.     }
  498.  
  499.       /* now shift all next members right as much as possible */
  500.     prev_pos = max_x;
  501.  
  502.     for (next = first; next != Prev_member(member); next = Prev_member(next))
  503.     {
  504.         X_position(next) = prev_pos - Half_width(next) - GAP/2;
  505.         prev_pos = X_left(next) - GAP/2;
  506.     }
  507.  
  508.       /**
  509.      We may have just shifted too far.  Shift members back to the left 
  510.      if possible
  511.        **/
  512.     if (X_position(member) > new_x)    
  513.     {
  514.         X_position(member) = new_x;
  515.     prev_pos = X_right(member) + GAP/2;
  516.  
  517.     for (next = Next_member(member); next != blocker; 
  518.          next = Next_member(next))
  519.     {
  520.             X_position(next) = prev_pos + GAP/2 + Half_width(next);
  521.             prev_pos = X_right(next) + GAP/2;
  522.     }
  523.     }
  524. } /* shift_right */
  525.  
  526. PLIST *sort_by_priority(level, direction)
  527. LEVEL *level;
  528. DIRECTION direction;
  529.   /**
  530.      sort_by_priority returns a list of the members in level sorted by
  531.      priority.
  532.    **/
  533. {
  534.     PLIST *plist;          /* the priority list */
  535.     PLIST *prev, *cur;     /* previous and current plist position */
  536.     MEMBER *member;        /* each member */
  537.  
  538.     plist = NULL;
  539.  
  540.     each_member(level, member)
  541.     loop
  542.         for (prev = NULL, cur = plist; (cur != NULL) && 
  543.          (Priority(cur->member, direction) > Priority(member, direction));
  544.          prev = cur, cur = cur->next)
  545.     {}
  546.  
  547.         new(cur, PLIST);
  548.         cur->member = member;
  549.  
  550.         if (prev == NULL)  /* add to the head of the list */
  551.         {
  552.         cur->next = plist;
  553.         plist = cur;
  554.         }
  555.         else /* add after prev */
  556.         {
  557.         cur->next = prev->next;
  558.         prev->next = cur;
  559.         }
  560.     endloop
  561.  
  562.     if (debug)
  563.     {
  564.         printf("\nsort_by_priority:  (%s)\n", 
  565.            (direction == UP) ? "UP" : ((direction == DOWN) ?
  566.                        "DOWN" : "UPDOWN"));
  567.         each_member_by_priority(plist, member)
  568.         loop
  569.         printf("   %s:   %d\n", Name(Member_node(member)),
  570.            Priority(member, direction));
  571.         endloop
  572.     }
  573.  
  574.     return(plist);
  575. } /* sort_by_priority */
  576.  
  577. dispose_plist(plist)
  578. PLIST *plist;
  579.   /**
  580.      dispose_plist disposes of each part of plist.
  581.    **/
  582. {
  583.     PLIST *next;    /* next to dispose */
  584.  
  585.     while (plist != NULL)
  586.     {
  587.         next = plist->next;
  588.         dispose(plist);
  589.         plist = next;
  590.     }
  591. } /* dispose_plist */
  592.  
  593. show_layout(digraph)
  594. DIGRAPH *digraph;
  595.   /**
  596.      show_layout prints the members in each level of digraph using their 
  597.      computed positions.
  598.    **/
  599. {
  600.     int column, left_pos;/* counters */
  601.     LEVEL *level;        /* each level */
  602.     MEMBER *member;      /* each member */
  603.  
  604.     printf("\n\nDigraph Levels (positioned):\n");
  605.  
  606.     each_level(digraph, level)
  607.     loop
  608.         column = 0;
  609.  
  610.         each_member(level, member)
  611.         loop
  612.         for (; column < X_left(member); column++)
  613.         {
  614.             printf(" ");
  615.         }
  616.  
  617.         if (column == X_left(member))
  618.         {
  619.             printf(".");
  620.             column++;
  621.         }
  622.  
  623.         left_pos = X_position(member) - strlen(Text(Member_node(member)))/2;
  624.  
  625.         for (; column < left_pos; column++)
  626.         {
  627.             printf("_");
  628.             printf("%s", Text(Member_node(member)));
  629.         }
  630.  
  631.         for (column += strlen(Text(Member_node(member)));
  632.              column < X_right(member); column++)
  633.         {
  634.             printf("_");
  635.         }
  636.  
  637.         printf(".");
  638.         column++;
  639.         endloop
  640.         printf("\n\n");
  641.     endloop
  642. } /* show_layout */
  643.  
  644. show_layout_numbers(digraph)
  645. DIGRAPH *digraph;
  646.   /* another debugging routine */
  647. {
  648.     LEVEL *level;
  649.     MEMBER *member;
  650.  
  651.     each_level(digraph, level)
  652.     loop
  653.     each_member(level, member)
  654.     loop
  655.         printf("%s(%d, %d)@(%d, %d)BC(Up:%d/Down:%d)  ",
  656.            Text(Member_node(member)),
  657.            2 * Half_width(member), 2 * Half_height(member),
  658.            X_position(member), Y_position(member),
  659.            (int) Bc(member, UP), (int) Bc(member, DOWN));
  660.     endloop;
  661.  
  662.     printf("\n");
  663.     endloop;
  664. } /* show_layout_numbers */
  665.  
  666. offset_levels(digraph)
  667. DIGRAPH *digraph;
  668.   /**
  669.      offset_levels computes the offset of each level of digraph.  This is done
  670.      by accounting for the longest arc between two levels.
  671.    **/
  672. {
  673.     LEVEL *level;    /* each level */
  674.     MEMBER *member;  /* each member */
  675.     VNO vno;         /* each antecedent */
  676.     int x, y;        /* right triangle parameters */
  677.     float minoffset, maxoffset;    /* min and max offsets in graph */
  678.     float alpha, scale, shift;
  679.  
  680.     minoffset = maxoffset = -1.0;
  681.  
  682.     each_level(digraph, level)
  683.     loop
  684.         Offset(level) = 0;    /* no offset yet */
  685.  
  686.         if (Prev_level(level) == NULL)   /* no previous level */
  687.         {
  688.         each_member(level, member)
  689.         loop
  690.             y = Half_height(member);
  691.  
  692.             if (y > Offset(level))    /* new maximum */
  693.         {
  694.                 Offset(level) = y;
  695.         }
  696.         endloop;
  697.         continue;
  698.         }
  699.  
  700.         each_member(level, member)
  701.         loop
  702.         each_element(Ante_set(Member_node(member)), vno)
  703.         loop
  704.             x = abs(X_position(Member(digraph, vno)) - X_position(member));
  705.                  /* offset should be at least 2/3 x value */
  706.             y = (2*(x + 1)) / 3 + Half_height(Member(digraph,vno)) + 
  707.             Half_height(member);
  708.  
  709.             if (y > Offset(level))      /* new maximum */
  710.         {
  711.                 Offset(level) = y;
  712.         }
  713.         endloop
  714.         endloop
  715.  
  716.         if (Offset(level) < MIN_OFFSET)    /* use default minimum */
  717.     {
  718.         Offset(level) = MIN_OFFSET;
  719.     }
  720.  
  721.         if (Offset(level) < minoffset || minoffset == -1)
  722.     {
  723.         minoffset = Offset(level);
  724.     }
  725.  
  726.         if (Offset(level) > maxoffset || maxoffset == -1)
  727.     {
  728.         maxoffset = Offset(level);
  729.     }
  730.     endloop
  731.  
  732.       /* Compress levels if the range of level offsets is too big.  */
  733.     if ((maxoffset - minoffset) / minoffset > MAX_OFFSET_PERCENT)
  734.     {
  735.     alpha = (maxoffset - (MAX_OFFSET_PERCENT + 1) * minoffset) /
  736.         (MAX_OFFSET_PERCENT + 2);
  737.     scale = (maxoffset - minoffset - 2 * alpha) / (maxoffset - minoffset);
  738.     shift = (minoffset + alpha) - scale * minoffset;
  739.     each_level(digraph, level)
  740.     loop
  741.         if (Prev_level(level) == NULL)
  742.         {
  743.         continue;
  744.         }
  745.  
  746.         Offset(level) = scale * (float) Offset(level) + shift;
  747.     endloop;
  748.     }
  749. } /* offset_levels */
  750.  
  751.  
  752. compute_y_positions(digraph)
  753. DIGRAPH *digraph;
  754.   /**
  755.      compute_y_positions uses the offset for each level to determine
  756.      the y value to put in each node.
  757.    **/
  758. {
  759.     LEVEL *level;    /* each level */
  760.     MEMBER *member;  /* each member */
  761.     int y;           /* y value for each level */ 
  762.  
  763.     y = MIN_OFFSET;
  764.  
  765.     each_level_reverse(digraph, level)
  766.     loop
  767.         each_member(level, member)
  768.         loop
  769.         Y_position(member) = y;
  770.         endloop
  771.  
  772.         y += Offset(level);    /* y value for level */ 
  773.     endloop
  774. } /* compute_y_positions */
  775.  
  776. straighten_all_dummies(digraph)
  777. DIGRAPH *digraph;
  778.   /**
  779.      straighten_all_dummies attempts to position dummy nodes in a vertical 
  780.      line 
  781.    **/
  782. {
  783.     NODE *node;
  784.     LEVEL *level;
  785.     int i;
  786.  
  787.     each_node(digraph, node)
  788.     loop
  789.         if (Is_dummy(node))
  790.     {
  791.         continue;
  792.     }
  793.  
  794.         straighten_dummies(digraph, node);
  795.     endloop
  796.  
  797.     for (i=0; i<3; i++)
  798.     {
  799.         each_level(digraph, level)
  800.         loop
  801.             adjust_positions(digraph, level, UP);
  802.         endloop
  803.  
  804.         each_level_reverse(digraph, level)
  805.         loop
  806.             adjust_positions(digraph, level, DOWN);
  807.         endloop
  808.     }
  809. }  /* straighten_all_dummies */
  810.  
  811. straighten_dummies(digraph, node)
  812. DIGRAPH *digraph;
  813. NODE *node;
  814.   /**
  815.      straighten_dummies follows the sequence of dummy nodes from each normal 
  816.      node and changes the x-positions to be the minimum value of all the dummy 
  817.      nodes in the sequence.
  818.      -> Changed 2/12/86 by ebm, so that x-position of dummy closest to node
  819.      starting chain is used.
  820.    **/
  821. {
  822.     NODE *next;
  823.     VNO vno;
  824.     int x_min;
  825.     int x_start;
  826.  
  827.     x_start = X_position(node);
  828.  
  829.     each_element(Succ_set(node), vno)
  830.     loop
  831.         next = Node(digraph, vno);
  832.  
  833.         if (!Is_dummy(next))
  834.     {
  835.         continue;
  836.     }
  837.  
  838.         x_min = X_position(next);
  839.  
  840.         do
  841.         {
  842.             if (abs(X_position(next) - x_start) < abs(x_min - x_start))
  843.         {
  844.                 x_min = X_position(next);
  845.         }
  846.  
  847.         next = next_dummy(digraph, next);
  848.         } while (Is_dummy(next));
  849.  
  850.         next = Node(digraph, vno);
  851.  
  852.         do
  853.         {
  854.         X_position(next) = x_min;
  855.             next = next_dummy(digraph, next);
  856.         } while (Is_dummy(next));
  857.     endloop
  858. }  /* straighten_dummies */
  859.  
  860. NODE *prev_dummy(digraph, node)
  861. DIGRAPH *digraph;
  862. NODE *node;
  863.   /**
  864.      prev_dummy returns a pointer to the next dummy node in the sequence 
  865.      If node is not a dummy node, this could give unexpected results
  866.    **/
  867. {
  868.     VNO vno;
  869.  
  870.     each_element(Ante_set(node), vno)
  871.     loop
  872.         return(Node(digraph, vno));    /* return the first ancestor found */
  873.     endloop
  874.     return (NULL);            /* error, no ancestor found */
  875. }  /* prev_dummy */
  876.  
  877. NODE *next_dummy(digraph, node)
  878. DIGRAPH *digraph;
  879. NODE *node;
  880.   /**
  881.      next_dummy returns a pointer to the next dummy node in the sequence 
  882.      If node is not a dummy node, this could give unexpected results.
  883.    **/
  884. {
  885.     VNO vno;
  886.  
  887.     each_element(Succ_set(node), vno)
  888.     loop
  889.         return(Node(digraph, vno));    /* return the first successor found */
  890.     endloop
  891.     return (NULL);            /* error, no successor found */
  892. }  /* next_dummy */
  893.  
  894. adjust_positions(digraph, level, direction)
  895. DIGRAPH *digraph;
  896. LEVEL *level;
  897. DIRECTION direction;
  898.   /** 
  899.      adjust_positions moves nodes to the right if necessary to avoid 
  900.      conflicting with the new positions of the dummy nodes. 
  901.    **/
  902. {
  903.     MEMBER *member;
  904.     int prev_pos;
  905.     int x_pos;
  906.     NODE *ante_node;
  907.     NODE *succ_node;
  908.  
  909.     prev_pos = MIN_X;
  910.  
  911.     each_member(level, member)
  912.     loop
  913.         x_pos = MAX(X_position(member), 
  914.             (prev_pos + GAP/2 + Half_width(member)));
  915.  
  916.         if (Is_dummy(member) && direction == UP)
  917.         {
  918.             ante_node = prev_dummy(digraph, member);
  919.  
  920.             if (Is_dummy(ante_node))
  921.         {
  922.                 x_pos = MAX(x_pos, X_position(ante_node));
  923.         }
  924.         }
  925.  
  926.         if (Is_dummy(member) && direction == DOWN)
  927.         {
  928.             succ_node = next_dummy(digraph, member);
  929.  
  930.             if (Is_dummy(succ_node))
  931.         {
  932.                 x_pos = MAX(x_pos, X_position(succ_node));
  933.         }
  934.         }
  935.  
  936.         X_position(member) = x_pos;
  937.         prev_pos = X_right(member) + GAP/2;
  938.     endloop
  939. }  /* adjust_positions */
  940.  
  941. float up_down_bc(member)
  942. MEMBER *member;
  943.   /* up_down_bc returns the average barycenter of the member */
  944. {
  945.     float bc, bc_up, bc_down;
  946.     int up_count, down_count;
  947.  
  948.     up_count = card(Ante_set(member));
  949.     down_count = card(Succ_set(member));
  950.     bc_up = Bc(member, UP);
  951.     bc_down = Bc(member, DOWN);
  952.  
  953.     if ((up_count + down_count) == 0)
  954.     {
  955.         bc = 0;
  956.     }
  957.     else
  958.     {
  959.         bc = (up_count * bc_up + down_count * bc_down) /
  960.          (up_count + down_count);
  961.     }
  962.  
  963.     return (bc);
  964. }
  965.  
  966. straighten_all_edges(digraph, str_mode)
  967. DIGRAPH *digraph;
  968. int str_mode;        /* straightening mode: bends allowed or not */
  969.   /**
  970.      straighten_all_edges attempts to draw all multi-segment edges as a small
  971.      number of straight line segments, without moving any regular nodes.
  972.    **/
  973. {
  974.     LEVEL *level;
  975.     NODE *member, *first_dummy, *last_dummy, *next_node;
  976.     VNO vno;
  977.  
  978.     each_level(digraph, level)
  979.     loop
  980.     if (debug3)
  981.     {
  982.         printf("level number %d : \n", Lno(level));
  983.     }
  984.  
  985.     each_member(level, member)
  986.     loop
  987.         if (debug3)
  988.         {
  989.         printf("    scanning node %s \n", Name(member));
  990.         }
  991.  
  992.         if (Is_dummy(member))
  993.         {
  994.         continue;
  995.         }
  996.  
  997.             each_element(Succ_set(member), vno)
  998.         loop
  999.         next_node = Node(digraph, vno);
  1000.  
  1001.         if (!Is_dummy(next_node))    /* must be dummy node */
  1002.         {
  1003.             continue;
  1004.         }
  1005.  
  1006.                 first_dummy = next_node;
  1007.                 last_dummy = next_node;
  1008.  
  1009.                 while (Is_dummy(next_node))    /* find next normal node */
  1010.         {
  1011.             last_dummy = next_node;
  1012.             next_node = next_dummy(digraph, next_node);
  1013.         }
  1014.  
  1015.         straighten_edge(digraph, member, first_dummy, last_dummy,
  1016.                        next_node, str_mode);
  1017.             endloop
  1018.         endloop
  1019.     endloop
  1020. } /* straighten_all_edges */
  1021.  
  1022. straighten_edge(digraph, node, first_dummy, last_dummy, next_node, straighten)
  1023. DIGRAPH *digraph;
  1024. NODE *node, *first_dummy, *last_dummy, *next_node;
  1025. BOOL straighten;    /* straightening mode: if true, does a better job */
  1026.   /**
  1027.      straighten_edge straightens the multi-segment edge running from node via
  1028.      first_dummy to next_node.  No normal nodes are moved.
  1029.    **/
  1030. {
  1031.     NODE *s_node, *s_dummy, *t_node;
  1032.  
  1033.     s_node = node;        /* starting node */
  1034.     s_dummy = first_dummy;    /* first dummy after starting node */
  1035.     t_node = next_node;        /* ending node */
  1036.  
  1037.     if (!straighten)    /* do a half-hearted job */
  1038.     {
  1039.     if (do_straighten(digraph, s_node, s_dummy, t_node))
  1040.     {
  1041.         if (debug3)
  1042.         {
  1043.             printf("\tstraightened edge from %s to %s\n", Name(s_node),
  1044.                Name(t_node));
  1045.         }
  1046.     }
  1047.     }
  1048.     else
  1049.     {
  1050.       /**
  1051.          work backward, adding the longest vertical segment possible,
  1052.          then a non-vertical segment, then try again.
  1053.          This looks strange, but okay.  Better schemes could be devised,
  1054.          but will probably waste a lot of time
  1055.        **/
  1056.         for (;;)
  1057.         {
  1058.         if (do_vertical(digraph, s_node, t_node))
  1059.         {
  1060.             if (debug3)
  1061.         {
  1062.                 printf("\tmade vertical edge from %s to %s\n", Name(s_node),
  1063.                    Name(t_node));
  1064.         }
  1065.  
  1066.         if (s_node == next_node)
  1067.         {
  1068.             t_node = last_dummy;
  1069.         }
  1070.         else
  1071.         {
  1072.             t_node = prev_dummy(digraph, s_node);
  1073.         }
  1074.  
  1075.             if (s_node == node || t_node == node)  /* reached node, done */
  1076.         {
  1077.             return;
  1078.         }
  1079.                 else
  1080.             {
  1081.             s_node = node;    /* try to draw segment from node */
  1082.                 }
  1083.             }
  1084.         else                 /* back up a level */
  1085.         {
  1086.             if (s_node == node)
  1087.         {
  1088.             s_node = first_dummy;
  1089.         }
  1090.             else
  1091.         {
  1092.                 s_node = next_dummy(digraph, s_node); 
  1093.         }
  1094.         }
  1095.         }
  1096.     }
  1097. } /* straighten_edge */
  1098.  
  1099. BOOL do_straighten(digraph, s_node, s_dummy, t_node)
  1100. DIGRAPH *digraph;
  1101. NODE *s_node, *s_dummy, *t_node;
  1102.   /**
  1103.      do_straighten calculates a straight line between s_node and t_node and
  1104.      then checks to see if the intervening dummy nodes could be moved to those
  1105.      positions without conflicting with other nodes.  If so, the x positions
  1106.      of the dummy nodes are changed, and a TRUE value is returned.  Otherwise,
  1107.      the x positions are unchanged and a FALSE value is returned.
  1108.    **/
  1109. {
  1110.     int x;            /* calculated straight line position of dummy */
  1111.     int x_s, x_t;        /* x positions of start and end nodes */
  1112.     int y_s, y_t;        /* y positions of start and end nodes */
  1113.     int x_min, x_max;        /* min and max dummy node positions */
  1114.     float slope;        /* slope (dx/dy) of straight line */
  1115.     NODE *curr;            /* current dummy node */
  1116.  
  1117.     if (s_dummy == t_node)    /* if single segment edge */
  1118.     {
  1119.     return (TRUE);
  1120.     }
  1121.  
  1122.     x_s = X_position(s_node);
  1123.     x_t = X_position(t_node);
  1124.     y_s = Y_position(s_node);
  1125.     y_t = Y_position(t_node);
  1126.     slope = ((float) (x_t - x_s)) / ((float) (y_t - y_s));
  1127.     curr = s_dummy;
  1128.  
  1129.     while (curr != t_node)
  1130.     {
  1131.     x = x_s + slope * (Y_position(curr) - y_s);
  1132.  
  1133.     if (Prev_member(curr) == NULL)
  1134.     {
  1135.         x_min = MIN_X;
  1136.     }
  1137.         else
  1138.     {
  1139.         x_min = X_right(Prev_member(curr)) + GAP / 2;
  1140.     }
  1141.  
  1142.     if (Next_member(curr) == NULL)
  1143.     {
  1144.         x_max = MIN_X;
  1145.     }
  1146.         else
  1147.     {
  1148.         x_max = X_left(Next_member(curr)) - GAP / 2;
  1149.     }
  1150.  
  1151.         if (x - Half_width(curr) < x_min || x + Half_width(curr) > x_max)
  1152.       /* if dummy runs into adj. node */
  1153.     {
  1154.         return (FALSE);
  1155.     }
  1156.  
  1157.     curr = next_dummy(digraph, curr);
  1158.     }
  1159.  
  1160.     curr = s_dummy;
  1161.  
  1162.     while (curr != t_node)
  1163.     {
  1164.     X_position(curr) = (int) (x_s + slope * (Y_position(curr) - y_s));
  1165.                 /* change position of dummy */
  1166.     curr = next_dummy(digraph, curr);
  1167.     }
  1168.  
  1169.     return (TRUE);
  1170. } /* do_straighten */
  1171.  
  1172. BOOL do_vertical(digraph, s_node, t_node)
  1173. DIGRAPH *digraph;
  1174. NODE *s_node, *t_node;
  1175.   /**
  1176.      do_vertical checks if you can draw a vertical line between s_node and 
  1177.      t_node If so, the x positions of the intervening nodes are changed, and 
  1178.      TRUE is returned.  Otherwise, the x positions are unchanged and 
  1179.      FALSE is returned.  If s_node or t_node is not a dummy, its x position
  1180.      will not be changed.  t_node's x position is never changed.
  1181.    **/
  1182. {
  1183.     int x;            /* calculated straight line position of dummy */
  1184.     int x_min, x_max;        /* min and max dummy node positions */
  1185.     NODE *curr;            /* current dummy node */
  1186.  
  1187.     if (!Is_dummy(s_node) && X_position(s_node) != X_position(t_node))    
  1188.       /* check if trying to change non-dummy */
  1189.     {
  1190.     return (FALSE);
  1191.     }
  1192.  
  1193.     x = X_position(t_node);
  1194.     curr = s_node;
  1195.  
  1196.     while (curr != t_node)
  1197.     {
  1198.     if (Prev_member(curr) == NULL)
  1199.     {
  1200.         x_min = MIN_X;
  1201.     }
  1202.         else
  1203.     {
  1204.         x_min = X_right(Prev_member(curr)) + GAP / 2;
  1205.     }
  1206.  
  1207.     if (Next_member(curr) == NULL)
  1208.     {
  1209.         x_max = MIN_X;
  1210.     }
  1211.         else
  1212.     {
  1213.         x_max = X_left(Next_member(curr)) - GAP / 2;
  1214.     }
  1215.  
  1216.         if (x - Half_width(curr) < x_min || x + Half_width(curr) > x_max)
  1217.           /* if dummy runs into adj. node */
  1218.     {
  1219.         return (FALSE);
  1220.     }
  1221.  
  1222.     curr = next_dummy(digraph, curr);
  1223.     }
  1224.  
  1225.     curr = s_node;
  1226.  
  1227.     while (curr != t_node)
  1228.     {
  1229.     X_position(curr) = x;             /* change position of nodes */
  1230.     curr = next_dummy(digraph, curr);
  1231.     }
  1232.  
  1233.     return (TRUE);
  1234.  
  1235. } /* do_vertical */
  1236.